home *** CD-ROM | disk | FTP | other *** search
/ Turnbull China Bikeride / Turnbull China Bikeride - Disc 1.iso / ARGONET / PD / GAMES / WIMPGAME / MINES2.ZIP / !Mines / c / bench next >
Text File  |  1995-01-28  |  25KB  |  860 lines
  1. /*  Benchmarking und "Uberpr"ufung der
  2. ** Optimierungen
  3. */
  4.  
  5. #include <stdio.h>
  6. #include <stdlib.h>
  7. #include <limits.h>
  8. #include <string.h>
  9. #include <time.h>
  10.  
  11. #define MINE 1      /* Flags für die Felder */
  12. #define MARK 2
  13. #define CLOSED 4
  14.  
  15. #define XMAX 30
  16. #define YMAX 16
  17.  
  18. #define FALSE 0
  19. #define TRUE 1
  20.  
  21. int feld[XMAX][YMAX] ;     /* DAS Spielfeld */
  22. int mines_left,fields_left; /* Zähler Variable */
  23. /* Richtungen zum Suchen */
  24. int off[8][2] = { {-1,-1},{0,-1},{1,-1},{-1,0},{1,0},{-1,1},{0,1},{1,1}};
  25.  
  26. /* Benchmarkanalysis */
  27. int freq_o[256]; /* frequency of domain of n elements without division */
  28. int steps_o[256]; /* ... */
  29. int freq[256]; /* Frequency of domain of n elements */
  30. int steps[256]; /* Sum of number of steps for a n-element-domain */
  31. int time_c,time_a; /* Time in centiseconds of calulation ( with assemlbly ) */
  32. int s;
  33.  
  34. int ende,err,overflow;
  35.  
  36. #define OBVIOUS 1
  37. #define HINT_DEBUG 2
  38. #define MARK_SET 3
  39. #define NO_MINE 4
  40. #define MINES_LEFT 5
  41. #define NEG_REST_FIELDS 6
  42. #define WRONG 7
  43. #define NOT_CLOSED 8
  44. #define UNKNOWN 255
  45.  
  46. /* Feder initialisieren (feld,bottom,vlines,lines)*/
  47. void res_feld()
  48. {int i,j ;
  49.  div_t r ;
  50.  mines_left=120;
  51.  fields_left = XMAX*YMAX-mines_left ;/* Freie Felder */
  52.  for( i = 0 ; i < XMAX ; i++ ) /* alle Felder ohne Mienen und geschlossen */
  53.     for( j = 0 ; j < YMAX ; j++ )
  54.        feld[ i ][ j ] = CLOSED ;
  55.  for( i=0 ; i<mines_left ;i++) /* jetzt ein paar Minen legen */
  56.     {do{r = div( rand() , XMAX ) ;
  57.         j = r.rem ;
  58.         r = div( rand() , YMAX ) ;
  59.        }while(feld[j][r.rem] & MINE) ;
  60.      feld[j][r.rem] |= MINE ;
  61.     }
  62. }
  63.  
  64. /* Anzahl der Minen um ein Feld zählen */
  65. int count(int x,int y)
  66. {int i,c=0,x1,y1 ;
  67.  for(i=0 ; i<8 ; i++)
  68.     {x1 = x+off[i][0] ;
  69.      y1 = y+off[i][1] ;
  70.      if(x1>=0 && x1<XMAX && y1>=0 && y1<YMAX)
  71.        if(feld[x1][y1] & MINE)
  72.          c++ ;
  73.     }
  74.  return c ;
  75. }
  76.  
  77. /* Ein Feld (gegebenenfalls mehrere rekursiv) oeffnen */
  78. void open_field(int x,int y)
  79. {int i ;
  80.  if(x>=0 && x<XMAX && y>=0 && y<YMAX && (feld[x][y] & CLOSED))
  81.    {
  82.     feld[x][y] &= ~CLOSED ;
  83.     fields_left-- ;
  84.     if(count(x,y) == 0)
  85.       {for(i=0;i<8;i++)
  86.          if( (feld[x+off[i][0]][y+off[i][1]] & CLOSED)
  87.              && !(feld[x+off[i][0]][y+off[i][1]] & MARK))
  88.             open_field(x+off[i][0],y+off[i][1]) ;
  89.       }
  90.    }
  91. }
  92.  
  93. void blotch(void)
  94. {int x,y,min,x1,y1;
  95.  int i,j,k,l,h ;
  96.  x = XMAX/2 ;
  97.  y = YMAX/2 ;
  98.  min = 9 ;
  99.  if(XMAX>YMAX)
  100.    j = x ;
  101.  else
  102.    j = y ;
  103.  if(x>=0 && x<XMAX && y>=0 && y<YMAX)
  104.    {if( !(feld[x][y] & MINE) && (feld[x][y] & CLOSED) )
  105.       {x1 = x ;
  106.        y1 = y ;
  107.        min = count(x,y) ;
  108.       }
  109.    }
  110.  x-- ;
  111.  y-- ;
  112.  for(i=1;i<=j;i++)
  113.    {for(l=0 ; l<4 ; l++)
  114.       {k = 2 * i + 1 ;
  115.        do{if(x>=0 && x<XMAX && y>=0 && y<YMAX)
  116.             {if( !(feld[x][y] & MINE) && (feld[x][y] & CLOSED) )
  117.                {h = count(x,y) ;
  118.                 if(h<min)
  119.                   {x1 = x ;
  120.                    y1 = y ;
  121.                    min = h ;
  122.                   }
  123.                }
  124.             }
  125.           k-- ;
  126.           if(k>0)
  127.             {switch(l)
  128.                {case 0:
  129.                   x++ ;
  130.                   break ;
  131.                 case 1:
  132.                   y++ ;
  133.                   break ;
  134.                 case 2:
  135.                   x-- ;
  136.                   break ;
  137.                 case 3:
  138.                   y-- ;
  139.                   break ;
  140.                }
  141.             }
  142.          }while(k>0) ;
  143.       }
  144.     x-- ;
  145.     y-- ;
  146.    }
  147.  if(min!=9)
  148.    open_field(x1,y1) ;
  149. }
  150.  
  151. #define in_playground(x,y) (((x)>=0) && ((x)<XMAX) && ((y)>=0) && ((y)<YMAX))
  152.  
  153. int move_wrong(int x0,int y0)
  154. {
  155.     return ((feld[x0][y0] & MARK) && !(feld[x0][y0] & MINE));
  156. }
  157.  
  158. int move_obvious(int x0,int y0)
  159. {
  160.     int mines=0,marks=0,unknown=0,d;
  161.     if (feld[x0][y0] & CLOSED) return(FALSE);
  162.     for (d=0;d<8;d++)
  163.     {
  164.         int x1=x0+off[d][0],y1=y0+off[d][1];
  165.         if (in_playground(x1,y1))
  166.         {
  167.             register char f=feld[x1][y1];
  168.             if (f & CLOSED) {if (f & MARK) marks++; else unknown++;};
  169.             if (f & MINE) mines++;
  170.         }
  171.     }
  172.     if ((unknown!=0) && ((marks==mines) || (marks+unknown==mines))) return(TRUE);
  173.     return(FALSE);
  174. }
  175.  
  176. typedef struct {char x,y,test,domain;} border_typ;
  177. border_typ *border_arr,*border_anz,*last_border_arr=0,*last_border_anz;
  178. int *minmax=0,*lastminmax=0;
  179.  
  180. #include "HintA.h"
  181.  
  182. #define min(domain) minmax[(domain)*2]
  183. #define max(domain) minmax[(domain)*2+1]
  184. #define last_min(last_domain) lastminmax[(last_domain)*2]
  185. #define last_max(last_domain) lastminmax[(last_domain)*2+1]
  186.  
  187. int find_next(int *x,int *y)
  188. {
  189.     /*
  190.     ** sucht das naechste Feld, dass sowohl bedeckte als auch unbedeckte
  191.     ** Felder als Nachbarn hat und selbst bedeckt ist, aber keine Marke
  192.     ** hat.
  193.     */
  194.     int closed_neighbors,open_neighbors,d;
  195.     do {
  196.         open_neighbors=0;closed_neighbors=0;
  197.         *x+=1;if (*x>=XMAX) {*x=0;*y+=1;};
  198.         if (*y<YMAX)
  199.             for (d=0;d<8;d++)
  200.             {
  201.                 int newx=*x+off[d][0],newy=*y+off[d][1];
  202.                 if (in_playground(newx,newy))
  203.                     {if (feld[newx][newy] & CLOSED) closed_neighbors++;
  204.                         else open_neighbors++;};
  205.             }
  206.     } while ((*y<YMAX) && ((feld[*x][*y] & MARK) || !(feld[*x][*y] & CLOSED) || (open_neighbors==0) || (closed_neighbors==0)));
  207.     if (*y>=YMAX) return FALSE;
  208.     return TRUE;
  209. }
  210.  
  211. border_typ *find_field(int x,int y,border_typ *i)
  212. {
  213.     while ((i<border_anz) && ((i->x!=x) || (i->y!=y))) i++;
  214.     if ((x==i->x) && (y==i->y) && (i<border_anz)) return i;
  215.     return 0;
  216. }
  217.  
  218. border_typ *exchange_field(border_typ *end_domain,border_typ *i,char domain)
  219. {
  220.     border_typ d;
  221.     if (i==0) return end_domain;
  222.     end_domain++;
  223.     d=*end_domain;*end_domain=*i;*i=d;
  224.     end_domain->domain=domain;
  225.     return end_domain;
  226. }
  227.  
  228. border_typ *find_neighbors(int x0,int y0,border_typ *end_domain,char domain)
  229. {
  230.     char d;
  231.     for (d=0;d<8;d++)
  232.        end_domain=exchange_field(end_domain,
  233.                   find_field(x0+off[d][0],y0+off[d][1],end_domain+1),
  234.                   domain);
  235.     return end_domain;
  236. }
  237.  
  238. void find_domains(border_typ *border,char domain)
  239. {
  240.     /*
  241.     ** Sortiert border_arr in unabhaengige Gebiete, die durch
  242.     ** ein (0,YMAX) getrennt sind
  243.     */
  244.     char d;
  245.     border_typ *end_domain=border;
  246.     border->domain=domain;
  247.     do {
  248.         for (d=0;d<8;d++)
  249.         {
  250.             int x=border->x+off[d][0];
  251.             int y=border->y+off[d][1];
  252.             if (in_playground(x,y) && !(feld[x][y] & CLOSED))
  253.                 end_domain=find_neighbors(x,y,end_domain,domain);
  254.         }
  255.         border++;
  256.     } while ((border->domain==domain) && (border<border_anz));
  257. }
  258.  
  259. void find_testmode(border_typ *border,char domain)
  260. {
  261.     while ((border->domain==domain) && (border<border_anz))
  262.     {
  263.         border_typ *ptr=border+1;
  264.         char x,y;
  265.         x=border->x;y=border->y;border->test=0;
  266.         while ((ptr->domain==domain) && (ptr<border_anz))
  267.         {
  268.             char x1=ptr->x,y1=ptr->y;
  269.             if (y1+2==y)
  270.             {
  271.                 if (x1+2==x) border->test|=1;
  272.                 if (x1+1==x) border->test|=1+2;
  273.                 if (x1==x)   border->test|=1+2+4;
  274.                 if (x1==x+1) border->test|=2+4;
  275.                 if (x1==x+2) border->test|=4;
  276.             }
  277.             if (y1+1==y)
  278.             {
  279.                 if (x1+2==x) border->test|=1+8;
  280.                 if (x1+1==x) border->test|=1+2+8;
  281.                 if (x1==x)   border->test|=1+2+4+8+16;
  282.                 if (x1==x+1) border->test|=2+4+16;
  283.                 if (x1==x+2) border->test|=4+16;
  284.             }
  285.             if (y1==y)
  286.             {
  287.                 if (x1+2==x) border->test|=1+8+32;
  288.                 if (x1+1==x) border->test|=1+2+8+32+64;
  289.                 if (x1==x+1) border->test|=2+4+16+64+128;
  290.                 if (x1==x+2) border->test|=4+16+128;
  291.             }
  292.             if (y1==y+1)
  293.             {
  294.                 if (x1+2==x) border->test|=8+32;
  295.                 if (x1+1==x) border->test|=8+32+64;
  296.                 if (x1==x)   border->test|=8+16+32+64+128;
  297.                 if (x1==x+1) border->test|=16+64+128;
  298.                 if (x1==x+2) border->test|=16+128;
  299.             }
  300.             if (y1==y+2)
  301.             {
  302.                 if (x1+2==x) border->test|=32;
  303.                 if (x1+1==x) border->test|=32+64;
  304.                 if (x1==x)   border->test|=32+64+128;
  305.                 if (x1==x+1) border->test|=64+128;
  306.                 if (x1==x+2) border->test|=128;
  307.             }
  308.             ptr++;
  309.         } /* while (ptr->domain==domain) */
  310.         border++;
  311.     } /* while (border->domain==domain) */
  312. }
  313.  
  314. FILE *f;
  315.  
  316. char find_last_domain(border_typ *border)
  317. {
  318.     border_typ *ptr=last_border_arr;
  319.     while ((ptr<last_border_anz) &&
  320.            ((border->x!=ptr->x) || (border->y!=ptr->y)))
  321.            ptr++;
  322.     if (ptr>=last_border_anz) return 0;
  323.     return ptr->domain;
  324. }
  325.  
  326. char find_new_domain(border_typ *last_border)
  327. {
  328.     border_typ *ptr=border_arr;
  329.     while ((ptr<border_anz) &&
  330.            ((last_border->x!=ptr->x) || (last_border->y!=ptr->y)))
  331.           ptr++;
  332.     if (ptr>=border_anz) return 0;
  333.     return ptr->domain;
  334. }
  335.  
  336. void look_for_old_domain(border_typ *border,char domain)
  337. {
  338.     border_typ *ptr,*border2=border;
  339.     char last_domain;
  340.     if (last_border_arr==0) return;
  341.     if ((last_domain=find_last_domain(border2))==0) return;
  342.     do { border2++;
  343.     } while ((border2<border_anz) && (border2->domain==domain) &&
  344.              (last_domain==find_last_domain(border2)));
  345.     if ((border2<border_anz) && (border2->domain==domain)) return;
  346.     ptr=last_border_arr;
  347.     while ((ptr->domain!=last_domain) && (ptr<last_border_anz)) ptr++;
  348.     if (ptr>=last_border_anz) return;
  349.     while ((ptr<last_border_anz) && (ptr->domain==last_domain) &&
  350.            (domain==find_new_domain(ptr)))
  351.           ptr++;
  352.     if ((ptr<last_border_anz) && (ptr->domain==last_domain)) return;
  353.     min(domain)=last_min(last_domain);
  354.     max(domain)=last_max(last_domain);
  355. }
  356.  
  357. void werr(int x,char *s)
  358. { printf("%s\n",s);if (x) exit(1);err=UNKNOWN;ende=TRUE;return;}
  359.  
  360. void init_border()
  361. {
  362.     border_typ *border;
  363.     int x,y;
  364.     char domain;
  365.     /*border_arr=malloc((XMAX*YMAX+1)*sizeof(border_typ));*/
  366.     border_anz=border_arr;x=-1;y=0;
  367.     if (border_arr==0) {werr(TRUE,"Could not allocate memory");return;};
  368.     while (find_next(&x,&y)) /* create border list */
  369.     {
  370.         border_anz->x=x;border_anz->y=y;border_anz->domain=0;
  371.         border_anz++;
  372.     }
  373.     if (border_anz==border_arr) return;
  374.     domain=1;border=border_arr; /* sort border list in domains */
  375.     do {
  376.         if (border<border_anz) find_domains(border,domain);
  377.         while ((border->domain==domain) && (border<border_anz))  border++;
  378.         domain++;
  379.     } while (border<border_anz);
  380.     /*x=border_anz-border_arr;
  381.     border_arr=realloc(border_arr,x*sizeof(border_typ));
  382.     if (border_arr==NULL)
  383.       {border_anz=border_arr;werr(FALSE,"Could not move memory");return;};
  384.     border_anz=border_arr+x;*/
  385.     for (border=border_arr;border<border_anz;border++)
  386.         if (feld[border->x][border->y] & MARK) werr(FALSE,"Mine found");
  387.     minmax=malloc(2*sizeof(int)*domain);
  388.     for (x=1;x<domain;x++) {min(x)=INT_MAX;max(x)=INT_MIN;};
  389.     domain=1;border=border_arr;
  390.     do {
  391.         if (border<border_anz) look_for_old_domain(border,domain);
  392.         while ((border->domain==domain) && (border<border_anz)) border++;
  393.         domain++;
  394.     } while (border<border_anz);
  395.     domain=1;border=border_arr; /* calculate the testmodes */
  396.     do {
  397.         if (border<border_anz) find_testmode(border,domain);
  398.         while ((border->domain==domain) && (border<border_anz))  border++;
  399.         domain++;
  400.     } while (border<border_anz);
  401. }
  402.  
  403. #define h_MASK 192
  404. #define h_EVERYTHING 0
  405. #define h_NOMINE 64
  406. #define h_MINE 128
  407. #define h_UNKNOWN 192
  408.  
  409. void exit_border()
  410. {
  411.     /*border_typ *border;
  412.     for (border=border_arr;border<border_anz;border++)
  413.         feld[border->x][border->y]&=~h_MASK;*/
  414.     /*if (last_border_arr!=0) {free(last_border_arr);free(lastminmax);};*/
  415.     border_typ *b=last_border_arr;int *i=lastminmax;
  416.     last_border_arr=border_arr;last_border_anz=border_anz;
  417.     border_arr=b;
  418.     lastminmax=minmax;minmax=i;
  419. }
  420.  
  421. int otest_if_possible(border_typ *border_ptr)
  422. {
  423.     /* Testet, ob die Wahl dieses Feldes gegen Informationen
  424.        der Nachbarfelder verstoesst */
  425.     char d0,d1,mines,marks,x1,y1;
  426.     for (d0=0;d0<8;d0++)
  427.     {
  428.         x1=border_ptr->x+off[d0][0];
  429.         y1=border_ptr->y+off[d0][1];
  430.         if (in_playground(x1,y1) && !(feld[x1][y1] & CLOSED))
  431.         {
  432.             mines=0;marks=0;
  433.             for (d1=0;d1<8;d1++)
  434.             {
  435.                 char x2=x1+off[d1][0],y2=y1+off[d1][1];
  436.                 if (in_playground(x2,y2))
  437.                 {
  438.                     register char f=feld[x2][y2];
  439.                     if (f & MINE) mines++;
  440.                     if (f & MARK) marks++;
  441.                 }
  442.             }
  443.             if ((border_ptr->test & (1 << d0))!=0)
  444.                  { if (marks>mines) return FALSE; }
  445.             else { if (marks!=mines) return FALSE; }
  446.         }
  447.     }
  448.     return(TRUE);
  449. }
  450.  
  451. #define p_POSSIBLE TRUE
  452. #define p_IMPOSSIBLE FALSE
  453.  
  454. char permutate1(border_typ *border,int mine_anz,char domain)
  455. {
  456.     char x,y;
  457.     char p1=p_IMPOSSIBLE,p2=p_IMPOSSIBLE,f1,f2;
  458.     s+=1;
  459.     if ((border->domain!=domain) || (border>=border_anz))
  460.     {
  461.       if (mine_anz>max(domain)) max(domain)=mine_anz;
  462.       if (mine_anz<min(domain)) min(domain)=mine_anz;
  463.       return p_POSSIBLE;
  464.     }
  465.     x=border->x;y=border->y;
  466.     if (otest_if_possible(border)) p1=permutate1(border+1,mine_anz,domain);
  467.     feld[x][y]|=MARK;
  468.     if (otest_if_possible(border)) p2=permutate1(border+1,mine_anz+1,domain);
  469.     feld[x][y]&=~MARK;
  470.     f1=feld[x][y] & h_MASK;f2=feld[x][y] & ~h_MASK;
  471.     if (p1==p_POSSIBLE)
  472.     {
  473.       if ((f1==h_NOMINE) || (f1==h_EVERYTHING)) f1=h_NOMINE;
  474.       else f1=h_UNKNOWN;
  475.     }
  476.     if (p2==p_POSSIBLE)
  477.     {
  478.       if ((f1==h_MINE) || (f1==h_EVERYTHING)) f1=h_MINE;
  479.       else f1=h_UNKNOWN;
  480.     }
  481.     feld[x][y]=f2 | f1;
  482.     /*if (f1==h_UNKNOWN)*/ return(p1 | p2);
  483. }
  484.  
  485. char permutate2(border_typ *border,int mine_anz)
  486. {
  487.     char x,y;
  488.     char p1=p_IMPOSSIBLE,p2=p_IMPOSSIBLE,f1,f2;
  489.     s+=1;
  490.     if (border>=border_anz)
  491.        {
  492.          if (mines_left+fields_left-(border_anz-border_arr)>=mine_anz)
  493.            return p_POSSIBLE; else return p_IMPOSSIBLE;
  494.        }
  495.     x=border->x;y=border->y;
  496.     if (otest_if_possible(border))
  497.         p1=permutate2(border+1,mine_anz);
  498.     if (mine_anz>0)
  499.     {
  500.         feld[x][y]|=MARK;
  501.         if (otest_if_possible(border)) p2=permutate2(border+1,mine_anz-1);
  502.         feld[x][y]&=~MARK;
  503.     }
  504.     f1=feld[x][y] & h_MASK;f2=feld[x][y] & ~h_MASK;
  505.     if (p1==p_POSSIBLE)
  506.     {
  507.       if ((f1==h_NOMINE) || (f1==h_EVERYTHING)) f1=h_NOMINE;
  508.       else f1=h_UNKNOWN;
  509.     }
  510.     if (p2==p_POSSIBLE)
  511.     {
  512.       if ((f1==h_MINE) || (f1==h_EVERYTHING)) f1=h_MINE;
  513.       else f1=h_UNKNOWN;
  514.     }
  515.     feld[x][y]=f2 | f1;
  516.     /*if (f1==h_UNKNOWN)*/ return(p1 | p2);
  517. }
  518.  
  519. char apermutate1(border_typ *border,int mine_anz,char domain)
  520. {
  521.     char x,y;
  522.     char p1=p_IMPOSSIBLE,p2=p_IMPOSSIBLE,f1,f2;
  523.     if ((border->domain!=domain) || (border>=border_anz))
  524.     {
  525.       if (mine_anz>max(domain)) max(domain)=mine_anz;
  526.       if (mine_anz<min(domain)) min(domain)=mine_anz;
  527.       return p_POSSIBLE;
  528.     }
  529.     x=border->x;y=border->y;
  530.     if (test_if_possible(border,XMAX,YMAX,feld)) p1=apermutate1(border+1,mine_anz,domain);
  531.     feld[x][y]|=MARK;
  532.     if (test_if_possible(border,XMAX,YMAX,feld)) p2=apermutate1(border+1,mine_anz+1,domain);
  533.     feld[x][y]&=~MARK;
  534.     f1=feld[x][y] & h_MASK;f2=feld[x][y] & ~h_MASK;
  535.     if (p1==p_POSSIBLE)
  536.     {
  537.       if ((f1==h_NOMINE) || (f1==h_EVERYTHING)) f1=h_NOMINE;
  538.       else f1=h_UNKNOWN;
  539.     }
  540.     if (p2==p_POSSIBLE)
  541.     {
  542.       if ((f1==h_MINE) || (f1==h_EVERYTHING)) f1=h_MINE;
  543.       else f1=h_UNKNOWN;
  544.     }
  545.     feld[x][y]=f2 | f1;
  546.     /*if (f1==h_UNKNOWN)*/ return(p1 | p2);
  547. }
  548.  
  549. char apermutate2(border_typ *border,int mine_anz)
  550. {
  551.     char x,y;
  552.     char p1=p_IMPOSSIBLE,p2=p_IMPOSSIBLE,f1,f2;
  553.     if (border>=border_anz)
  554.        {
  555.          if (mines_left+fields_left-(border_anz-border_arr)>=mine_anz)
  556.            return p_POSSIBLE; else return p_IMPOSSIBLE;
  557.        }
  558.     x=border->x;y=border->y;
  559.     if (test_if_possible(border,XMAX,YMAX,feld))
  560.         p1=apermutate2(border+1,mine_anz);
  561.     if (mine_anz>0)
  562.     {
  563.         feld[x][y]|=MARK;
  564.         if (test_if_possible(border,XMAX,YMAX,feld)) p2=apermutate2(border+1,mine_anz-1);
  565.         feld[x][y]&=~MARK;
  566.     }
  567.     f1=feld[x][y] & h_MASK;f2=feld[x][y] & ~h_MASK;
  568.     if (p1==p_POSSIBLE)
  569.     {
  570.       if ((f1==h_NOMINE) || (f1==h_EVERYTHING)) f1=h_NOMINE;
  571.       else f1=h_UNKNOWN;
  572.     }
  573.     if (p2==p_POSSIBLE)
  574.     {
  575.       if ((f1==h_MINE) || (f1==h_EVERYTHING)) f1=h_MINE;
  576.       else f1=h_UNKNOWN;
  577.     }
  578.     feld[x][y]=f2 | f1;
  579.     /*if (f1==h_UNKNOWN)*/ return(p1 | p2);
  580. }
  581.  
  582. int set_mark(int x,int y)
  583. {
  584.   if (!(feld[x][y] & CLOSED)) {ende=TRUE;err=NOT_CLOSED;return TRUE;};
  585.   if (feld[x][y] & MARK) return FALSE;/*{ende=TRUE;err=MARK_SET;return TRUE;};*/
  586.   if (!(feld[x][y] & MINE)) {ende=TRUE;err=NO_MINE;return TRUE;};
  587.   if (mines_left==0) {ende=TRUE;err=MINES_LEFT;return TRUE;};
  588.   feld[x][y]|=MARK;mines_left-=1;return FALSE;
  589. }
  590.  
  591. int hint_debug(void)
  592. {
  593.     border_typ *border;
  594.     for (border=border_arr;border<border_anz;border++)
  595.         {
  596.             int d=feld[border->x][border->y];
  597.             if ((((d & h_MASK)==h_NOMINE) && (d & MINE)) ||
  598.                 (((d & h_MASK)==h_MINE) && !(d & MINE)))
  599.                 {err=HINT_DEBUG;ende=TRUE;return TRUE;};
  600.         }
  601.     return FALSE;
  602. }
  603.  
  604. void add_time(int t) {time_c+=t;}
  605. void add_timea(int t) {time_a+=t;}
  606. void inc(int *p) {*p+=1;}
  607. void add(int *p,int x) {*p+=x;}
  608.  
  609. /* ein Hinweis */
  610. int hint_it(void)
  611. {
  612.     char x,y,p=0,domain;
  613.     int closed_fields_without_border,max_mines,min_mines;
  614.     border_typ *border,*ptr;
  615.     /* Suche nach einem falschen Zug */
  616.     for (x=0;x<XMAX;x++)
  617.         for (y=0;y<YMAX;y++)
  618.             if (move_wrong(x,y))
  619.             {
  620.               ende=TRUE;err=WRONG;return TRUE;
  621.             }
  622.     /* Suche nach einem offensichtlichen Zug */
  623.     for (x=0;x<XMAX;x++)
  624.         for (y=0;y<YMAX;y++)
  625.             if (move_obvious(x,y))
  626.             {
  627.               ende=TRUE;err=OBVIOUS;return TRUE;
  628.             }
  629.     /* Suche nach einer eindeutigen Schlussfolgerung */
  630.     init_border();
  631.     if (border_anz==border_arr) {exit_border();blotch();return TRUE;};
  632.     border=border_arr;domain=1;max_mines=0;min_mines=0;
  633.     do {
  634.         if (max(domain)==INT_MIN)
  635.         {
  636.             int t;
  637.             for (ptr=border;ptr->domain==domain;ptr++)
  638.                 feld[ptr->x][ptr->y]&=~h_MASK;
  639.             s=0;t=clock();
  640.             permutate1(border,0,domain);
  641.             add_time(clock()-t);inc(&freq[ptr-border]);
  642.             add(&steps[ptr-border],s);
  643.             for (ptr=border;ptr->domain==domain;ptr++)
  644.                 feld[ptr->x][ptr->y]&=~h_MASK;
  645.             t=clock();
  646.             apermutate1(border,0,domain);
  647.             add_timea(clock()-t);
  648.         }
  649.         max_mines+=max(domain);min_mines+=min(domain);
  650.         while ((border->domain==domain) && (border<border_anz)) border++;
  651.         domain++;
  652.     } while (border<border_anz);
  653.     closed_fields_without_border=mines_left+fields_left - (border_anz-border_arr);
  654.     if (closed_fields_without_border<0)
  655.     { ende=TRUE;err=NEG_REST_FIELDS;return TRUE;}
  656.         {
  657.           int t;
  658.           for (ptr=border_arr;ptr<border_anz;ptr++)
  659.             feld[ptr->x][ptr->y]&=~h_MASK;
  660.           s=0;t=clock();
  661.           permutate2(border_arr,mines_left);
  662.           add_time(clock()-t);inc(&freq_o[border_anz-border_arr]);
  663.           add(&steps_o[border_anz-border_arr],s);
  664.           for (ptr=border_arr;ptr<border_anz;ptr++)
  665.             feld[ptr->x][ptr->y]&=~h_MASK;
  666.           t=clock();
  667.           apermutate2(border_arr,mines_left);
  668.           add_timea(clock()-t);
  669.     if ((max_mines>mines_left) ||
  670.         (closed_fields_without_border<mines_left-min_mines))
  671.           if (max_mines>mines_left) max_mines=mines_left;
  672.         }
  673.     if (closed_fields_without_border>0)
  674.     {
  675.       if (min_mines==mines_left)
  676.       {
  677.         int do_it=TRUE;
  678.         for (x=0;x<XMAX;x++) for (y=0;y<YMAX;y++)
  679.         {
  680.           for (ptr=border_arr;ptr<border_anz;ptr++)
  681.             if ((ptr->x==x) && (ptr->y==y)) do_it=FALSE;
  682.           if (do_it) open_field(ptr->x,ptr->y);
  683.         }
  684.       }
  685.       if (closed_fields_without_border==mines_left-max_mines)
  686.         for (x=0;x<XMAX;x++) for (y=0;y<YMAX;y++)
  687.         {
  688.           int do_it=TRUE;
  689.           for (ptr=border_arr;ptr<border_anz;ptr++)
  690.             if ((ptr->x==x) && (ptr->y==y)) do_it=FALSE;
  691.           if (do_it) if (set_mark(ptr->x,ptr->y)) return TRUE;
  692.         }
  693.     }
  694.     if (hint_debug()) return TRUE;
  695.     for (border=border_arr;border<border_anz;border++)
  696.     {
  697.         register unsigned char d=feld[border->x][border->y] & h_MASK;
  698.         if ((d==h_NOMINE) || (d==h_MINE)) p++;
  699.     }
  700.     if (p!=0) return FALSE;
  701.     border=&border_arr[rand() % (border_anz-border_arr)];
  702.     if (feld[border->x][border->y] & MINE)
  703.       set_mark(border->x,border->y);
  704.     else open_field(border->x,border->y);
  705.     exit_border();
  706.     return FALSE;
  707. }
  708.  
  709. void play(void)
  710. {
  711.   int x0,y0,change;
  712.   ende=FALSE;overflow=FALSE;err=FALSE;
  713.   do {
  714.     printf(".");
  715.     do {
  716.     change=FALSE;
  717.     for (x0=0;x0<XMAX;x0++)
  718.       for (y0=0;y0<YMAX;y0++)
  719.         if (!(feld[x0][y0] & CLOSED))
  720.         {
  721.             int mines=0,marks=0,unknown=0,d;
  722.             for (d=0;d<8;d++)
  723.             {
  724.                 int x1=x0+off[d][0],y1=y0+off[d][1];
  725.                 if (in_playground(x1,y1))
  726.                 {
  727.                     register char f=feld[x1][y1];
  728.                     if (f & CLOSED) {if (f & MARK) marks++; else unknown++;};
  729.                     if (f & MINE) mines++;
  730.                 }
  731.             }
  732.             if ((unknown!=0) && (marks==mines))
  733.             {
  734.               for (d=0;d<8;d++)
  735.               {
  736.                 int x1=x0+off[d][0],y1=y0+off[d][1];
  737.                 if ((in_playground(x1,y1)) && (feld[x1][y1] & CLOSED) && (!(feld[x1][y1] & MARK)))
  738.                 {
  739.                   open_field(x1,y1);
  740.                   change=TRUE;
  741.                 }
  742.               }
  743.             }
  744.             if ((unknown!=0) && (marks+unknown==mines))
  745.             {
  746.               for (d=0;d<8;d++)
  747.               {
  748.                 int x1=x0+off[d][0],y1=y0+off[d][1];
  749.                 if ((in_playground(x1,y1)) && (!(feld[x1][y1] & MARK)) && (feld[x1][y1] & CLOSED))
  750.                 {
  751.                   if (set_mark(x1,y1))
  752.                   {
  753.                     int x2,y2;
  754.                     for (y2=-1;y2<=1;y2++)
  755.                     {
  756.                       if (y2==0) printf("%2i ",x2-x0); else printf("   ");
  757.                       for (x2=-1;x2<=1;x2++)
  758.                         if (in_playground(x0+x2,y0+y2)) printf("%4i",feld[x0+x2][y0+y2]);
  759.                       printf("\n");
  760.                     }
  761.                     return;
  762.                   }
  763.                   change=TRUE;
  764.                 }
  765.               }
  766.             }
  767.         }
  768.     } while (change);
  769.     if (hint_it()) return;
  770.     for (x0=0;x0<XMAX;x0++)
  771.       for (y0=0;y0<YMAX;y0++)
  772.       {
  773.         if ((feld[x0][y0] & h_MASK)==h_MINE) if (set_mark(x0,y0)) return;
  774.         if ((feld[x0][y0] & h_MASK)==h_NOMINE) open_field(x0,y0);
  775.       }
  776.     if ((fields_left==0) || (mines_left==0)) ende=TRUE;
  777.   } while (!ende);
  778.   printf("\n");
  779. }
  780.  
  781. void init_bench(void)
  782. {
  783.   int i;
  784.   for (i=0;i<256;i++)
  785.   {
  786.     freq_o[i]=0;
  787.     steps_o[i]=0;
  788.     freq[i]=0;
  789.     steps[i]=0;
  790.   }
  791.   time_c=0;time_a=0;
  792. }
  793.  
  794. char ext[2]="A";
  795.  
  796. void save(void)
  797. {
  798.   FILE *f;
  799.   if (err)
  800.   {
  801.     printf("Error :%i\n",err);
  802.     if ((f=fopen("<Mines$Dir>.bencherr","ab"))==0) werr(TRUE,"File err");
  803.     fwrite(feld,XMAX*YMAX,sizeof(int),f);
  804.     fclose(f);
  805.     return;
  806.   }
  807.   if (overflow)
  808.   {
  809.     printf("Overflow");
  810.     rename("<Mines$Dir>.benchmark",strcat("<Mines$Dir>.benchmark",ext));
  811.     ext[0]+=1;
  812.     init_bench();
  813.     return;
  814.   }
  815.   if ((f=fopen("<Mines$Dir>.benchmark","wb"))==0) werr(TRUE,"File err");
  816.   fwrite(freq_o,256,sizeof(int),f);
  817.   fwrite(steps_o,256,sizeof(int),f);
  818.   fwrite(freq,256,sizeof(int),f);
  819.   fwrite(steps,256,sizeof(int),f);
  820.   fwrite(&time_c,1,sizeof(int),f);
  821.   fwrite(&time_a,1,sizeof(int),f);
  822.   fclose(f);
  823. }
  824.  
  825. int main(void)
  826. {
  827.   int x,y,c;
  828.   printf("init");
  829.   init_bench();
  830.   border_arr=malloc(XMAX*YMAX*sizeof(border_typ));
  831.   last_border_arr=malloc(XMAX*YMAX*sizeof(border_typ));
  832.   last_border_anz=last_border_arr;
  833.   minmax=malloc(256*sizeof(int));
  834.   lastminmax=malloc(256*sizeof(int));
  835.   printf("done\n");
  836.   do {
  837.     printf("res_feld\n");
  838.     res_feld();
  839.     printf("blotch\n");
  840.     blotch();
  841.     printf("play");
  842.     play();
  843.     printf("\n");
  844.     for (y=0;y<YMAX;y++)
  845.     {
  846.       for (x=0;x<XMAX;x++)
  847.        if (feld[x][y] & CLOSED)
  848.        {
  849.          if (feld[x][y] & MARK) printf("*"); else printf(".");
  850.        }
  851.        else
  852.          if ((c=count(x,y))==0) printf(" "); else printf("%i",c);
  853.       printf("\n");
  854.     }
  855.     printf("save\n");
  856.     save();
  857.   } while (TRUE);
  858.   return 0;
  859. }
  860.